{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machinery Transport Planning\n",
    "\n",
    "## Try me\n",
    " [![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/MIP/solved/Machinery%20Transport%20Planning%20(Solved).ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FMIP%2Fsolved%2FMachinery%20Transport%20Planning%20(Solved).ipynb)\n",
    "\n",
    "## Problem Definition\n",
    "A firm must transport machines from production plants A, B and C to warehouses X, Y and Z. Five machines are required in X, four in Y and three in Z and there are eight machines available in A, five in B and three in C.\n",
    "**a)** Contemplate and solve a Graph Theory model to determine the maximal flow of the machines that can be transported and the run of this flow.\n",
    "**b)** By assuming a mean cost of €45 per transported machine, what would the total cost be of transporting the machines obtained in the former section?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Requirements\n",
    "Run the following script to install the packages used in the exercise:\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "!pip install networkx\n",
    "!pip install matplotlib\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Solution\n",
    "We are going to use [networkx] (https://networkx.github.io/) to draw the network and find the maximal flow at a minimum cost between two nodes. We are going to create a graph to model the transport process, the network will comprise the Source node (node S), production plant nodes (nodes A, B, and C), warehouse nodes (nodes X, Y, and Z), and a sink node (node T). Edges are going to have two attributes: \n",
    "\n",
    "- $b_i$: maximum capacity (number of machines) of each production plant or warehouse\n",
    "- $c_i$: cost, cost for the company to move one machine (€).\n",
    "\n",
    "The flow of edges going from source node S to each production plant represent the available machines at each production plant. These edges have a capacity equal to machines available at each production plant, and a cost of 0;  \n",
    "The flow of edges going from each production plant to each warehouse represents the machines transported by the company from each production plant to each warehouse. The edges will have a maximum capacity equal to the machines available at each production plan, and a cost of 45€. \n",
    "Finally, flow in edges from the warehouse nodes to the sink node represent the total number of machines in each warehouse.  These edges will have a maximum capacity equal to the demand  of each warehouse, a company cost of 0.\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAdUAAAE/CAYAAAAQZlkTAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4zLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvnQurowAAIABJREFUeJzt3Xd4FOXaBvB7N2VTCCEKGEKvISSECEg30luQIohKRxSUYkHgCHggVo6CR4UjHBVpIkjvvYpAqAqEAAl4qNKkBtJ3Z74/+CYGSdkys1P2/l0XlyTZnXnkhbn3eWZ21iSKoggiIiJymVntAoiIiIyCoUpERCQThioREZFMGKpEREQyYagSERHJhKFKREQkE4YqERGRTBiqREREMmGoEhERyYShSkREJBOGKhERkUwYqkRERDJhqBIREcmEoUpERCQThioREZFMGKpEREQyYagSERHJhKFKREQkE2+1CyBSmiAIEAQh92uz2Qyzma8njYBrS1rDUCVDslqtyMrKgtVqhSiKj/zcZDLB29sbFosF3t78Z6AnXFvSMpOY399KIp2y2WxIT0+HzWaz+zleXl4ICAiAl5eXgpWRq7i2pAcMVTKMzMxMZGZmOv18Pz8/+Pn5yVgRyYVrS3rBUCVDyMjIQFZWlsvbsVgs8Pf3l6EikgvXlvSEZ/RJ9zIzM2U56AJAVlaWSx0RyYtrS3rDUCVds9lssh8oMzMzHTpvR8rg2pIeMVRJ19LT03W1XbIf15b0iKFKumW1Wu3qOvbt24cXX3wRVapUQWhoKJ588kmMGTMG2dnZBT7HZrPBarXKWS45oKi1XbBgAUJCQgr8VRiuLSmJFyqRbqWlpSEnJ6fQxyxbtgxDhgyBzWZDVFQU6tatiwsXLmD37t04c+YMgoODC3yuj48PAgMD5S5bUZmZmYiNjc19H2ePHj3w/vvvq12Ww4pa28OHD2Pp0qW5XwuCgLlz5yIrKwv16tXD1q1bC92+HteW9IGhSrp19+7dfN/8L0lPT0dUVBRu376Nnj17YsaMGbl32zl79izKli0LX1/fAp9vMpkKDV0tEkURaWlpKFasGHJyctCsWTN89dVXaNSokdqlFWnbtm24f/8+unTpUuTa/t3HH3+MKVOmICQkBDt37kSFChUKfbwe15b0geNf0iVBEIo86O7fvx+3b98GAIwaNeqh29dVrly50EAFHgRU3lvg6YHJZEKxYsUAADk5OcjJyYHJZFK5KvsMGzYMXbt2RbVq1Ry6mGjbtm3497//DZPJhBkzZhQZqIA+15b0gffwIl2y54D4559/5v6+fPnyDu8jIyMDU6ZMwYULFxx+rju0adMGL7zwwiMvDmw2G+rVq4czZ85g2LBhaNiwYe7Pbty4gZEjR7q7VLtcuXIFABAcHIx79+7Z1Un+8ccfGDJkCARBwFtvvYV27drZvT9BEHifYJIdQ5UMq1SpUrm/v3jxIqpXr+7Q861WK06fPo2jR4/KXZosatSokW+37uXlhSNHjuDOnTvo1q0bjh8/jqioKABAdnY2Dhw44O5S7ZKRkQHgwU0a7GG1WvHyyy/j5s2baNKkCd577z0lyyOyC0OVDKtBgwYoUaIE7ty5gylTpjx0TvXChQsoU6YMfHx8Cnx+UFAQfvzxR93elL1EiRJo3rw5Nm7cmBuqYWFhOHXqlMqV5a9mzZpITk5GTk5OkaN5AIiPj8eBAwdQunRpfP/997y/L2kCL1QiXRIEAampqUU+bvHixXj99dchCAKioqJQr149XLlyBTt37kRKSkqRI8bixYvrakT4559/wsfHByVKlEBGRgbatm2Lf/zjH+jUqZPapRXps88+w8mTJ/Gf//ynyKu6N2/ejBdeeAEA0KhRI8TExDz08zFjxhT51hq9rS3pgz5fgpPHM5vNMJlMRV6s1LNnT5QtWxZfffUVDh48iJSUFISFhaFfv35F3gfWZDLp7qB75coV9O/fHzabDYIgoGfPnroIVOBBEEqKuvr3119/zf39vn37sG/fvod+/vrrrxcaqnpcW9IHdqqkW/a8T9UVfC+jeri2pFd8qUa6Ze8FLVrdPhWMa0t6xVAl3fL29lbs4hQvLy/dXqBkBFxb0iuGKunWoUOHMGrUqNy3YsgpICBA9m2S/X799VeMHj2aa0u6w5drpFtNmjTJPe82YcIEWc6RiaIIf39/vj1DZY0aNUJOTg5EUeTakq6wUyXdmj9/PgDg22+/xcyZM13+7M2MjAzMmDEDN27ckKM8csGCBQsAcG1JfxiqpFsLFizIfVtEfHy8ywfM4OBgLFiwABEREbh06ZIcJZKT/r62kyZNQnp6utMf2VaiRAksXLgQERERmr3tJBkDQ5V0qUuXLli3bh12796Nn376CdHR0YiKikJQUJDd4z1BEJCeng6bzYagoCAEBATgyJEjqFixIoNVRd26dcOaNWuwa9cuLFmyBD4+Ppg6dSpiY2Nx9OhRhz5k3MvLC0FBQfD398fRo0dRqVIl1KpVi8FKiuH7VEl3nn32WWzcuBG7du1C48aN832M1WrN/UzR/P6Km0wmeHt7o1u3bjCbzdi4cWPuzwRBQHR0NM6fP4+TJ0+iXLlyiv2/0MO6du2KdevWYefOnWjatCkA4OrVq+jSpUvuPYvr1KmDPXv2FLm2Fovlkat8BUFATEwM/ve//+HEiRN2faINkSMYqqQrUqDu3r37oU9fKYwgCA99qo3ZbM4dLa5evRpdu3bFpUuXEBYW9tBz6tSpg3PnziEpKYkHXzeQAjW/F0vR0dEwmUwoXbo0/vjjD5w4cQJA4WtbEAYrKYmhSrrRqVMnbNq0yaFAtUelSpUQHh6OTZs2PfR9KVjPnj3Lg6/CunTpgvXr1+cbqIcOHUKDBg1w7Nix3A8GcFXeYE1KSkLFihVl2S4RQ5V0IS4uDps3b5Y9UAFg7dq16Ny58yPdKsCuxh2KGudHR0fDYrHg4MGDsu5XEAQ8+eST+P333xmsJBuGKmmeFKh79+7FU089pcg+CupWAQarkooa5x88eBANGzZEYmIiIiMjZd+/IAioW7cuzpw5w2AlWTBUSdM6duyIrVu3Ys+ePYoFKgCsX78enTp1woULF/K9MInjQvnZM85XqkvNi8FKcmKokmZ16NAB27ZtUzxQJZUqVUKNGjWwefPmfH/OcaF87Bnn79+/H40bN1asS81LEATUq1cPKSkpOH78OCpXrqzo/si4GKqkSVKg7t27F/Xr13fLPovqVgF2NXKwd5xfu3Zt+Pv7576VRmmCIKB+/fpITk5msJLTGKqkOe3bt8f27dvdGqiSypUro1q1atiyZUuBj2GwOs/ecb47u9S8GKzkKoYqaUq7du2wY8cOVQIVsK9bBTgudIYj4/yoqCgEBgZi//79bqruL4Ig4KmnnsKpU6e4tuQwhipphtqBKrGnWwXY1TjCkXG+1KUmJSUhIiLCTRU+TBAENGjQACdOnEBSUhLXluzGUCVNaNu2LXbu3Il9+/ahbt26qtayYcMGxMXF4dy5c0W+fYbBWjRHx/lqdql55Q3WxMREVK1aVdV6SB8YqqS6Nm3aYNeuXUhISFA9UCVVqlRBlSpVsHXr1iIfy3FhwRydPiQkJKBp06aqdql5MVjJUQxVUpUUqPv370dMTIza5eTatGkTOnToYFe3CnBcmB8pUB2ZPkRGRiIoKAj79u1TuDr7CYKAhg0bIikpicFKRWKokmpat26NX375RXOBKqlatSoqVaqEbdu22fV4djV/cWacL3WpJ0+eRHh4uMIVOobBSvZiqJIqWrVqhd27d2s2UAHHu1WAwQo4P86vVasWgoODkZCQoGB1zhMEAY0aNcLx48dx9OhRVK9eXe2SSIMYquR2eghUiaPdKuDZXY2z4/w9e/bg6aef1mSXmpcgCLnvn2WwUn4YquRWLVu2xJ49e3Dw4EFER0erXU6RtmzZgnbt2uHs2bMO3eQhb1fjKcHqyjhf611qXoIgoEmTJjh27BiDlR7BUCW3adGiBfbu3aubQJVUrVoVFStWxPbt2x16nieNC12ZPuilS81LCtajR4/iyJEjuqmblMdQJbfQa6ACznergGeMC10d50dERCAkJAR79+5VoDrlCIKApk2b4siRIwxWysVQJcU1b94cCQkJOHz4MKKiotQuxynVqlVD+fLlsWPHDoefa+RxoavjfKlLTU5O1uWfiyAIaNasGX777TcGKwFgqJLCmjdvjn379uHQoUO6DVQA2LZtG9q0aeNUtwoYc1wox/QhIiICjz32GPbs2SNzde7DYKW8GKqkGKMEqsSVbhUw1rhQjkDdvXs3YmNjddul5iUIAp5++mn8+uuvul9bcg1DlWQnCAJatGiB/fv3GyZQAde7VcAYXY1c43wjdKl5CYKA2NhYHD58GL/++qsmbrNI7sdQJVkJgoDmzZvjwIEDOHz4sFs/C9MdqlevjrJly2Lnzp1Ob0PPwSrX9GHXrl1o3ry5IbrUvBisxFAl2Rg9UAFg+/btaN26tUvdKqDPcaGc4/yaNWuiZMmS2L17t0zVaYcgCHjmmWdw8OBB/PbbbwxWD8NQJVnkPZAYNVAlNWrUQJkyZfDzzz+7tB29dDVyj/OlLvX06dOGvSmGJ7zApPwxVMllUjgcOnTII16ZS93q77//7vKn0Wg9WJUIh/DwcJQuXRq//PKLDBVqF4PVMzFUySWeFqgSubpVQLvjQiVCYefOnWjZsqWhu9S88nb5DFbPwFAlp+U9L6jFLktJUjjI0a0C2utqlBrne0qX+nfS+WgtrC0pi6FKTsl7BaunBaqkRo0aCA0Nxa5du2TZnlaCVanpg6d1qX9ntPdtU/4YquQwPb8lRE5KhITa40Ilx/lyvwjRIwar8TFUySFGuiuQHJQaZ6oxLlRynC/3uFzPWrRogYSEBAarQTFUyW5GvH+tq5Qcabqzq1F6nC/nhV1GoOdPbaLCMVTJLnkD9dixY4a6C46rlLz4xh3BqvQ4X863IBmJq5/wQ9rEUKUiSZ8JeuzYMQZqPpS+mYHU1Sjx0XnuGOezSy2Y9Fm0DFbjYKhSoQRBQKNGjXD8+HHDfRaonJS+7Z4S40J3jPPl+BACo3P1Q95JWxiqVCAGqv3c8TFmco4L3TXOl+MDCDxB69at8csvvzBYDYChSvkSBAENGzZEUlISEhMTPfJ9hY5yx0eZyTEudNc4n12qY9q0aYNdu3YxWHWOoUqPEAQBDRo0wIkTJxioDnDXh267Mi505/TB1Q9190QMVv1jqNJDGKiucdcHb0vjwkOHDqF27dp2Pcedgcou1Xlt27bFzp07sW/fPtStW1ftcshBZrULIO1goLpu5syZSEhIQHJysqL72bp1K+Li4mCxWCAIgl3Pyc7ORvny5ZGYmKj4+fEhQ4bgmWeeYaA6YfPmzWjRogUaNWqEX3/9Ve1yyEHsVAkAIIoi1q9fj549e+LYsWMMVBdEREQgJCQEe/fuVXxf2dnZ8PX1tfvxgiDAbFb2tfSWLVvQrl07dqkuateuHQRBwMaNG+Hl5aV2OWQnhqqHOXHiBK5fv47atWvj8ccff+hnaWlpEAQBQUFBKlVnDHv27MHTTz+NkydPauKuU0lJSbh+/TpatGjhlv1VrVoVFStWxPbt292yPyPLzMyEn59fgT9399pS0Tj+9SAbN27ECy+8gKlTp6JPnz64cuXKQz8PDAxkoMqgadOmqFmzJgYMGKB2KQCAa9euYciQIdiwYYPi+9qyZQvOnj2LOXPmKL4vT1BYoALuXVuyk0geYefOnWL16tXFhIQEURRF8bnnnhM3btyoclXGtXfvXtFkMomnTp1SZf+CIDz09f79+8XatWuLx48fV3S/VapUEVu2bKnoPjydWmtL9mGn6iFCQ0Px3//+F40aNcK1a9eQkJCAGTNmYPDgwViyZAlEngWQVePGjREREaFat2oymQAAH330Ea5cuYIGDRqgSpUquHHjhmL73LRpE86ePYvZs2crtg9SZ23JfgxVDxEeHo6WLVsCAGbNmoXXX38dK1euRJMmTbB06VL8+eefKldoPDNnzsT+/ftx8uRJt+0zJycHWVlZuV+bTCbUq1cPXbt2hc1ms/vtN84YOnQoWrRogQoVKii2D0+m5tqS/XihEiEuLg7vv/8+6tevr3YphhMZGYmgoCDs27fPLftbv349rly5gkGDBuV+r2vXrhgxYgRq166N0qVLK7LfDRs2IC4uDufOnWOoKkSttSXHsFP1cMuXL8fVq1dRtmxZtUsxpFmzZuHAgQNu61arVq2Kf//731i2bBkAYPbs2XjiiSfQqlUrRQ+6w4YNQ8uWLRmoClJrbckx7FQ9VFZWFn788UdMmTIFixYt4uhIQVFRUQgMDMT+/fvdsr+kpCT0798fpUuXRvHixdGjRw/06NFDsf1JXeqFCxdQrlw5xfZD7l9bchxD1QMIgoCMjAwEBgbmfi8nJwdbtmxBlSpVULNmTRWrM779+/ejcePGSEpKQkREhFv2ee3aNVy+fBnly5fH448/nntxixIqV66MatWqYcuWLYrtg/7y97VNT09HamoqypQpo3ZpBIaq4QmCgJiYGAQHB+Pnn39W/G46lL/atWsjICBA1m5VFEVkZWUV+V7GvGw2m6x351m/fj06derELlVFq1atQo8ePbBr1y40btxY7XI8Ho+wBiYF6tmzZ/Hjjz8yUFU0c+ZMHDx4EElJSbJsT7o5fmJiot33/s3IyECLFi1kDfZhw4ahVatWDFQVdenSBXFxcYiNjUVCQoLa5Xg8HmUNShAE1KlTB2fPnkVSUhIvIFFZw4YNERkZiYEDB7q8LenFUlJSEkJDQ+1+seTv74/g4GA0a9ZMlmBdv349zp8/z/elasDKlSsZrBrB8a8BCYKA6OhonD9/HidPnmQXoREHDx5Ew4YNkZiYiMjISKe2IQXq//73P5w4ccKpF0tdunTB+vXrXR4XVqpUCTVq1MDmzZud3gbJq2vXrli3bh127tyJpk2bql2OR2KoGozVakVMTAwDVaOio6NhsVhw8OBBh5+bd5zv6vRBOvg6G6w8l6pd3bp1w9q1axmsKmGoGojVakWdOnVw4cIFBqpGOdutSuP8c+fOyTbOdyVYK1WqhPDwcGzatMnlOkh+zz33HNasWcNgVQFD1SCkQL148SJOnDjBQNUwR7tVJcf5zowL165di86dO+PSpUsICwuTrRaSlxSsO3bsQLNmzdQux2MwVA3AarUiOjoaly5dwqlTp3ig07hDhw6hQYMGOHbsGKKiogp9rDvG+Y6OC9ml6kf37t2xevVqBqsbMVR1zmq1onbt2vjjjz8YqDoSHR0NX19fHDp0qMDHuHOcb++4cPXq1ejatSu7VB3p0aMHVq1axWB1E4aqjjFQ9auoblWNcb4948KKFSsiIiICGzduVLwekg+D1X0YqjolBerly5dx8uRJBqoO1alTBz4+Po90q2qO8wsbF7JL1bfnn38eK1aswPbt2xEbG6t2OYbFUNUhq9WKqKgoXLlyhYGqY7/++ivq16+PI0eOIDo6GoA2pg8FdTUVKlRAZGQkNmzY4PaaSB49e/bE8uXLGawKYqjqDAPVWGJiYuDt7Y1Dhw5pIlAlfw/WVatWoVu3brh8+TJCQ0NVq4tcJwXr1q1b0bx5c7XLMRyGqo7kDdTk5GQe3AxA6lYPHTqE3r17a2qcn3dc2KdPH3apBvLiiy9i6dKlDFYFMFR1wmq1IjIyEteuXcOpU6cYqAZSp04dJCcnw2KxaCZQJT179sSyZcsgCAKuXLnCv3cGwmBVBm+orwNWqxW1atVioBqQ1WrF3bt3kZWVhWXLlmkqUAFg8eLFsFgsMJlMOHXqlNrlkIx++uknPP/882jdujW2b9+udjmGwVDVOClQr1+/zkA1GGmcf/v2bURFRWHMmDFql/SIFStWIDMzE88++yxat26NnTt3ql0SyWjhwoXo2bMn2rZty2CVCce/GpY3UFNSUlC6dGm1SyKZSOP8q1evIjk5GVevXkXdunXx66+/IiYmRu3ycpUvXx7R0dFYt24dx4UG1qtXLyxevBibN29Gy5Yt1S5H1xiqGsVANa6Cpg9169YF8ODiJS1YsWIFunfvjqtXr+b+/XvppZewZMkSHnwNqHfv3li0aBE2bdqEVq1aqV2ObjFUNSg7OxuRkZG4ceMGkpOTGagGUtg4/8iRI5rqVvN2qXmxqzGuPn364KeffmKwuoChqjHZ2dmoVasWbt68yUA1GHumD3Xr1oUoivjtt99UqPAvy5YtQ8+ePXHlypV862SwGheD1TUMVQ3Jzs5GREQEbt26xUA1GGn68OeffxY6zj927BhiYmJw6NCh3HGwGsqVK4eYmBisXbu2wMdwXGhcUrBu2LABbdq0UbscXWGoakTeQD19+jRKliypdkkkE0fH+fXq1YPNZsORI0fcVOHDiupS82JXY1z9+vXDggULGKwOYqhqgBSot2/fRkpKCgPVQJwZ56vdrZYrVw5PPvkk1qxZY9fjGazG1b9/f/z4448MVgcwVFXGQDUuV8b59evXR05ODo4ePapghY9aunQpXnjhBbu61Lw4LjQuKVjXrVuHdu3aqV2O5jFUVZSdnY2aNWvizp07DFSDcXWcL3WrBw4cQP369RWq8lGOdql5cVxoXAMGDMAPP/yA9evXM1iLwFBViRSod+/eRXJyMgPVQOQ6P+7ubnXx4sV46aWXcO3aNadr5rjQuAYOHIh58+YxWIvAUFVBdnY2wsPDkZqaitOnT+Oxxx5TuySSiZzj/OPHjyM6Otpt3WrZsmVRv359rFq1yqXtcFxoXFKwrl27Fh06dFC7HE1iqLpZdnY2atSogXv37jFQDUaJcX79+vWRnZ2NY8eOyVBhweToUvPiuNC4Xn75ZcydO5fBWgCGqhtlZmaiZs2aDFQDUur8uLu61bCwMDRo0AArV66UbZvsaoxLCtY1a9agY8eOapejKQxVN5EC9f79+0hJSWGgGkjecb4S58efeuopZGVlKdatLlq0CL169ZKtS82LwWpcr7zyCmbPns1g/RuGqhswUI3LHeP8pKQk1K5dG/v378dTTz0l+/bDwsLQsGFDrFixQvZtAxwXGtmrr76KWbNmMVjzYKgqLDMzE+Hh4UhLS2OgGow7x/lKdatSl/rnn38qWj/HhcYlBeuqVavQqVMntctRHUNVQXkD9cyZMyhRooTaJZFM3H1+XOpWExIS0LBhQ9m2q3SXmhfHhcbFYP0LQ1UhmZmZqFGjBtLT0xmoBqPWOL9BgwbIyMhAYmKiLNtbuHAh+vTpo3iXmhfHhcY1ePBgfP/991ixYgU6d+6sdjmqYagqQArUjIwMnD59moFqIGqO8+XuVsuUKYPGjRtj+fLlMlRnP3Y1xvXaa6/hu+++8+hgZajKTArUzMxMpKSkMFANRAvj/IYNGyItLQ3Hjx93aTtqdKl5MViNy9ODlaEqo8zMTFSvXh1ZWVkMVIPRyjj/5MmTiIyMdLlbLVOmDJo0aYJly5bJWJ1jOC40rtdffx3ffvstli9fji5duqhdjlsxVGWSnp6O8PBwBqoBaW2c72q3+uOPP6Jfv36qdal5eXpXY2SeGqwMVRmkp6ejRo0ayM7OxpkzZ1C8eHG1SyKZaC1Qgb+61T179qBx48YOP18LXWpeDFbjGjp0KL755huPClaGqoukQM3JycHp06cZqAai5XF+o0aNcO/ePSQlJTn0vPnz56N///64efOmpv5/PLWr8QTDhg3Df//7XyxduhTdunVTuxzFMVRdwEA1Lq2P85OTkxEREeFwtxoaGopmzZph6dKlClbnHAarcXlSsDJU/58gCBAEIfdrs9kMs9lc4OMZqPrh7NpmZ2drMlAljRs3xt27d3HixAm7Hq/VLjUvR8eFjq4tqcfRYNXr2np0qFqtVmRlZcFqtSK/PwaTyQRvb29YLBZ4e3vnfj89PR3Vq1eHzWZDSkoKA1WDXFlbvZwfl7rVX375BU2bNi3y8U888QRiY2OxZMkSN1TnvLwH30uXLuFf//oXLl68mHtAdXZtSX0jRozA9OnTsXjxYly7dg0fffQRLl26ZKi19chQtdlsSE9Ph81ms/s5Xl5eCAgIQFZWFgNVw1xdW71NH+ztVufNm4eBAwdqukvNa9iwYZg+fXru18uXL0fnzp2dXlsvLy8lyiQnvPHGG5g2bVru10uWLEG3bt0Ms7ba76VllpmZiXv37jm0eMCDg/W9e/cwceJEBqpGubq277//vq4CFQDmzJmDU6dOYc+ePYU+bvTo0Xjuued0EagAULNmzYe+PnXqlEtrm5mZKWd55IK/r21KSoqh1tajOtWMjAxkZWW5tI309HQEBgYiODhYpqpIDnKtbUBAgG6CR7JkyRLExsbiiSeeyPfn2dnZ2Lt3L+rWraubFwu+vr7IyckBAMTHx+OVV15BYGCgS9u0WCzw9/eXozxygcViQXZ2NgBjrq3HhGpmZqasr2j8/Pzg5+cn2/bIeZ6+tqIowmQyufwYLbl+/Tr+9a9/wWQyYeTIkS4fdCV6W1sjun79Oj799FMAMOTaekSoSmMCuQUFBWlunu9puLbGxbU1LiOvrUecU01PT9fVdsl+XFvj4toal5HX1vCharVaizwBfu7cOfTt2xfVq1dHaGgoIiMj0aNHD5w9e7bQ59lsNlitVjnLdZtKlSqhdu3aiImJQf369dUuxylFrW10dDRCQkIQEhKCkiVLIjw8HH369MG5c+eK3Lae19YICltbURQRFxeHkJAQ9OrVK/f7N2/eRJUqVRASEvLQlcN/p/e1tdlsePLJJ3X76T6O/LvN79fu3bsLfK4W1labb/SRkT0Xr/Tp0wdJSUmIjY1F1apVcfnyZezduxdXr15F5cqVi9y+Vt8vVZQdO3agZMmSapfhNHsvTGrXrh0qVqyI7du3Y926dUhNTcXq1avt2r5e1zY/9+/fR7FixdQuwy6Fra3JZMJXX32FZs2aYcOGDVi/fj06duyICRMm4Pbt23jyyScxZMiQIrev17X96quvEBERgdTUVLVLcUpR/2779OmD27dvAwBmzZqF7OxsdO7cGWFhYQCQ+9/Ctq/ZVTFFAAAgAElEQVTm2urzb5UDinrVcvv2bSQlJSE4OBgrV67MvZgjKyvLrku81X5V5GlGjhyJxMREzJ071+4LHPr27Yu4uDhs2LABvXr1wunTp+16npHWdv/+/Rg/fjy2bt2qdikFGj16NH777TfMmzevyLWtVq0aRo0ahY8//hhjx46Fv78/Fi5cCG9vb3z11VdFnlfT69peunQJ69atw/jx4/Hvf/9b7XLsNmbMGBw6dAjz5s1DUFBQkY+VLFiwANnZ2Xj11VfRrFkzu/al9toaevwrCEK+d+XIq1ixYihWrBju3r2L2NhYjB8/HuvWrYPVakVAQECR+xBF8aFbaemFyWRC27ZtUa9ePXz77bdql2O31atXY+vWrahVq1buWy6K8sMPP+Af//gH4uPjAQDPPvusXc/T69rm93de+uzVFStWuLscu61Zswbbtm2ze23ffPNN1KpVCxcuXMCLL74IURQxYsQI1K5du8jn6nVt33rrLXz22We6uF1fXmvXrsWOHTsQFRVl979bZ6m9tobuVO35g/Xx8cHUqVPx1ltv4fjx4zh+/DimT5+O0qVLY+HChahbt26hz7937x569OiBxMREucqW1TvvvPPQKz/Jnj17EBYWhuvXr6NNmzaoWbMmYmNjAQC3bt1CRESEu0u1y40bNwAAVatWRVpaml3vF960aVPu7y0WC2JiYuzalxbXtmnTpli2bFmBb49JTU1Feno6QkNDAQCrVq3C6dOnMWrUKIwcORKzZs3Kve/qkSNH0K5dO7fVXhRH11b6t9u2bVtkZ2ejatWq+f5dz48W1zavgQMHYuLEiQ+993Lt2rUoXbo06tWrh507dz7ynD/++KPI45Vabt68CcCxf7euEARBtRcehg5Ve3Xr1g0dOnTAnj17kJCQgHnz5uH69euYPHkyFi5cWOhzfXx80KNHD6c+19IdCroISTovUbp0aXTr1g0HDhzIDVU/Pz8MHjzYbTU64uuvv8bt27dhsVjsfs78+fPRsWNHHD58GB07dsSIESPQtGlTVKxYsdDnaXFtizqfNHfuXFy9ehUff/wxgAd3r3nppZdQo0YNzJs3D3Xq1IHNZoPZbEZQUJCm1nn69Om4deuWQ2tbr149NGjQAPv27cOAAQPsfp+iFtc2rwYNGjxyXnDPnj1YvXo11q9fj8zMTKSmpqJPnz6YP38+gAdTNy2tZ14zZszAzZs3HVpbvfL4UM3JycGhQ4fQuHFjtGrVCq1atcLjjz+OcePG4f79+0U+38/PD6+88oquLnpIS0uDIAgICgpCWloaNm/ejAkTJuT+PCAgAB9++KGKFRZs8eLFuH37NsqUKePQRTcmkwkxMTEICAjA3bt3cfbs2SJDVY9rGxcXh+7du+eGamZmJtq1a4ft27ejUqVKePXVV3PPN1atWlVT67xs2TLcunULoaGhDq2t9P/jyPsT9bi2kyZNwqRJkwAAO3fuxJQpU3IDFQCCg4M1tZ55rVy5Ejdv3nR4bfVIP3+jnGBP+5+VlYWOHTsiPDwctWvXRkBAANauXQsAaN68uWz70ZJr167ljgCtVit69eqF9u3bq1yVfRYtWgTgwWX39l79+MMPP+CXX37B0aNHcffuXQQEBCAyMtKu5+ptbatUqYK6deti8ODBKF26NG7fvo3nn38evXr1UnUkZo+ffvoJgiA4tLau0PKfhdH8+OOPsFqtiImJMfzaGj5UTSZToRcr+fn5YejQofjll1+wZcsWZGZmIiwsDIMGDcKbb75Z5D5MJpPu/nFWqVIFR48eVbsMp+Q9H1rU2kqkc6rBwcFo1KgRxo4di1KlShX5PD2uLQBMnjwZS5YswcWLF1G/fn10794dgPZDJDo6Ovf39q6ts/S6tpLmzZvb/aJfCzxpbQ1/m8K0tDRFrzbz8fGR7d6V5BiurXFxbY3L6Gur35dqdlL6xLgnnHjXKq6tcXFtjcvoa2v4UPX29lbsBsteXl66utDBaLi2xiWtrRKDNK6tuoy+toYPVQB23cRBS9sl+3FtH7zZXfpV2M/1ZNiwYWjSpAkyMjJk37ae1taIRowYYei19YqXbjNjYNJJa7luXyXdbcnX11eW7ZHzuLYPbtkXFBRU4Bv/7969iyZNmqB69eqoUqWKm6tzTu/evXHx4kXcv38fTZo0kW09/Pz8dLW2RtSrVy9Dr61HdKrAgz9wOWbt2dnZ+Prrr7Fs2TIZqiI5yL22S5culaEq9/jmm29w/vx59OzZs8DHlChRAsHBwXjttdfcWJlrDh48CAD49ttvMXPmTGRnZ7u8TYvFookPsfZ0hw8fBvDX2tr7wRiF0dLaekyoAoC/v7/Lf/DFixdHeno6+vXrhx9//FGmyshVcq1tVlYW+vXrh3nz5slUmbLGjRuHXr16FfmG+rlz5+L333/Htm3b3FSZ8+7cuYOmTZuiTJky8Pf3R3x8vF0fblEYPz+/h275R+pITU1FkyZN8MQTTyAgIADx8fEuXwmstbX1uLP1fn5+8PHxQXp6ukP/UL28vBAQEAAvLy98+umnMJvN6Nu3L4AHoypSnxxr+8knnwAABgwYAADo16+fEqXKYsaMGUhNTS30s0MlFStWxDPPPIMhQ4bgzJkzbqjOOXfu3EGNGjVgsViQnJyM+/fv4/vvv0eZMmVgs9lcWltSV2pqKqpVqwZfX1+kpKTg/v37+O6771CuXDlDra3h36daGKvViqysLFit1nwv5DCZTPD29obFYsn3irKxY8fi008/xbx589CnTx93lEx2cnVtx48fj0mTJmHOnDmaDdbHH38cnTp1wty5c+16/Pnz51G5cmVs2bIFrVq1Urg6x925cwfVq1eHn58fTp8+XeDkwdW1JfeTXixJgVrQBUVGWFttVuUm3t7euQsjCMJDn2pjNpuLvCvHpEmTYDKZcg+6DFbtcHVtP/74Y5jNZgwYMACiKKJ///6K1uuo6dOnIzU1FV9//bXdz6lYsSKaN2+uyW5VClR/f3+kpKQUOsp3dW3Jvf4+fSjsCl0jrK1Hh2pezi6YNC7s168fBEHQbFfjyZxdW+nm5AMHDoQgCBg4cKDcpTntn//8p13nUv9u9uzZud1qmzZtFKrOMXfu3EG1atUQEBBQZKD+nV4OtJ7KkUD9O72uLUNVBp988glMJpMuzsORY6RgHTRoEABoIlilLnXGjBkOP1fqVl977TX8/vvvClTnGFcClbTN3nG+0TBUZZJ3XAgwWI3kww8/hMlk0kywvvfee+jdu7fTb3SfM2cOKlWqpHq3euvWLdSoUQOBgYFITk72mIOuJ3BknG80DFUZSV2NVs/DkfM++OADAA86VkEQcgPW3f7zn//g3r17dl3xW5AKFSqgRYsWqnarUqAWK1YMp06d8qiDrtF5+vSBoSozLZ+HI9d88MEHMJvNePXVVwFAlWCdMGEC+vTp4/Lt2GbPno1KlSph06ZNaNeunUzV2efWrVuoXr06goKCGKgG4+mBCjBUFaG1cSHJJz4+HiaTCa+++ipEUcQrr7zitn1PmzYN9+7dc+iK34JUqFABLVu2xNChQ93arTJQjYvj/AcYqgrJOy4EGKxGMnHiRADA4MGDAcBtwTpx4kRZulTJrFmzUKlSJWzYsAEdOnSQZZuFYaAaF8f5f2GoKkgaF6p9Ho7k5+5glbNLlUjd6rBhw/C///1Ptu3m58aNGwgPD0dQUBBSUlI0ceNzkgdfLD2MoaqwvONCQJ3zcKSMiRMnwmQyYfDgwRAEITdglTBhwgT07dtX9o+2mjNnDipUqKBot3rjxg3UqFEDwcHBSE5OZqAaCAP1UQxVN5C6GjXOw5GyJkyYALPZjNdeew2iKGLIkCGy7+Orr77C/fv38Z///Ef2bZcrVw6tWrXC0KFDcfbsWdm3LwVqiRIlcOrUKQaqgeSdPjBQ/8JQdRO1zsOR8t577z0AwOuvvw4AsgdrfHw8+vfvr9gHMM+ePRsVKlTA+vXr0bFjR9m2y0A1Lo7zC8ZQdaO840KAwWok7733Hkwmk+zB+uWXXyrWpUrKlSuH1q1bY9iwYbJ1q1KghoSE4OTJkzzoGgjH+YVjqLqZNC50x3k4cq/x48cDeNCxCoKQG7CueP/999G/f3/FR2uzZs2SrVu9fv06wsPD8dhjjzFQDYbTh6IxVFUgjQuVPA9H6pCCddiwYQDgUrC6o0uVSN3q0KFDce7cOae3w0A1LgaqfRiqKlFqXEjqGz9+PMxmM4YNGwZRFDF06FCnthMfH48BAwa47QKQOXPmoFy5ck53q1KgPv744zhx4gQPugbCcb79GKoqyjsuBBisRjJ27FgAwPDhwwHA4WD98ssvkZ6ejmnTpsleW0HCwsLQpk0bp7pVKVBLliyJpKQkHnQNhNMHxzBUVabEeTjShrFjx8JkMjkcrIIguL1LlcyePRvlypXD2rVr0alTJ7uec/36ddSoUQOlSpVioBoMA9VxDFUNkGtcSNrz7rvvwmw2Y/jw4RAEITdgCyN1qVOnTnVDhQ8LCwtD27ZtMXz4cLtCVQrU0qVL4/jx4zzoGgjH+c5hqGqEq+NC0q4xY8YAAN544w2IoogRI0YU+FhBEPDBBx+o0qVKZs2ahXLlymH16tXo3LlzgY+7evUqatasidKlS+PEiRPw9ubhxCg4znce/xVoiLPjQtI+KVjffPNNACgwWL/44gvVulSJ1K2OGDGiwFBloBoXx/mu4b8EjXn33XcBwKFxIenDmDFjYDKZCgxWqUt9+eWXVb/l25w5cxAWFpZvt3r16lWEh4fjiSeeYKAaDMf5MhBJkz799FPRZDKJ06ZNU7sUktlnn30mmkwm8csvv3zo+1OmTBF9fHzEjIwMlSp7WPv27cXy5cs/9L0rV66IxYsXF2vUqCHm5OSoVBkp4cqVK2JwcLBYvXp1rq0LGKoaJgXr1KlT1S6FZDZlypSHgtVms4nFixcXX3vtNZUr+8uVK1dEk8kkrly5MvdrBqoxMVDlw7mNhhU1LiT9eueddwAAb7/9NkRRRE5ODjIyMvDFF1+oXNlfQkND0b59e4wYMQJPPfUUIiIiUKZMGRw/fpwjXwPhOF9e/NPTuNGjRwMo+gIX0h8pWEeOHAlfX18MGjRI9XOpfzdr1iyEhYWhWrVqqFixIhITE3nQNRApUENDQ5GUlMS1lQH/BHVg9OjRMJvNePPNNyEIQm7Akv6988472LFjB9atW4cqVaqoXc4jBEGA2WxGTk4OA9VgGKjK8IqPj49XuwgqWpMmTVCsWDG88847CA4ORqNGjdQuiWQg3UWrfv36mD17NoKCgtC4cWO1ywIAXL58GTVr1kS5cuVw69YtxMTEICIiQu2ySAbS2pYpU4aBKjOGqo5IwTpq1CgGq0FMnjwZW7ZsQXJyMh577DG88847KFasGJo0aaJqXZcuXUJERATKlSuHpKQkHDp0CHPmzMHIkSNVrYtcJwVq2bJleX5cCWpfKUWO+/zzz0WTySR+8cUXapdCLrDZbGJQUJA4dOjQ3O99+eWXoslkEqdMmaJaXRcvXhSLFSsmRkRE5F4Jeu3aNdFsNovLly9XrS5y3R9//CEGBQWJNWvW5FW+CmGo6tQXX3whmkwm8fPPP1e7FHLSpEmTRF9fXzErK+uh70vB+tlnn7m9JilQa9Wq9chBNy4uTixXrpzbayJ5MFDdg6GqYwxW/cqvS81LjWCVAjUyMjLfg67UrS5dutRtNZE8Ll68KAYFBT00fSBlMFR1TgvjQnLcJ598km+XmtfUqVPdFqznz58vNFAlcXFxYtmyZRWvh+ST3ziflMNQNQA1x4XkOJvNJhYrVkwcPnx4kY+VgvXTTz9VrJ68gWqz2Qp9LLtVfSlsnE/KYKgaBINVP+zpUvOaNm2aaDKZxEmTJsley/nz58XAwEAxKiqqyECVdOrUid2qDhQ1zidlMFQNxJ3jQnKO1KWOGDHCoecpEazOBKoo/tWtLlmyRLZaSF72jvNJfgxVg3HHuJCc99FHHznUpeb19ddfiyaTSfzkk09crkMK1Nq1azsUqJLOnTuzW9UoR8b5JD+GqgFJXQ2DVVuc7VLzkiNYz50751KgiqIo/vnnn6LZbBYXLVrkdB0kP2enDyQfhqpBKXkejpzz4YcfihaLxakuNa/p06c7HaxyBKqkS5cuYlhYmEvbIPkwULWBoWpgco4LyTU2m00MDAwU33jjDVm2JwXrnDlz7H5OamqqGBgYKEZHR8ty0GW3qh2ujvNJPgxVg2OwaoNcXWpey5cvF+/du2f34+/fvy8uWbJE1oNuly5dxDJlysi2PXLcpUuXGKgaYhJFUVT7/sOkrBkzZiAzMxPDhg2Dr6/vIz+/c+cOrFYrSpYsqUJ1xicIAooXL45XX31VlQ8hP3HiBO7cuYMmTZpAFEWYTCbZtn3r1i2UKlUKCxYswAsvvCDbdsk+oiji5s2b6NevH9auXQuz2ax2SR6PoeohcnJy4OPj88j3Fy9ejGnTpsHf3x/Dhw9H586dVajO2D744AN88sknuH//vts/EeS3335Dp06dYLVa8cMPP6Bt27ay76Nbt27Yv38/Ll++LPu26YF169YhOTk5308JstlsMJvNsr5YIheo2SaTum7duiU++eST4vLly8XExESxdu3aYkJCgtplGYp0LvWtt95y+74TExPFSpUqiWvWrBH3798v1qlTR1y9erXs+7l586ZoNpvFn376SfZtkyhu3rxZjImJETdt2qR2KWQHfpCeB7pz5w727t2L7du3w8fHB61atULx4sURExOD33//nZ/TKqMPP/wQVqsVkydPdvu+f/75Z+Tk5KBRo0YoWbIkpkyZgpMnT8q+n8ceewxdunTB22+/zRGwzPbt24fevXtjzZo1aNiwIe7evYs7d+6gVKlSCAgIULs8ygdD1QPNnTsXR44cQY8ePRAcHIw6deqgefPmSE9PR9WqVdUuzzAEQcDkyZMxdOhQt419xf8/m2MymTBs2DBYLBY8//zzWLFiBVq3bo3WrVsrst+ZM2eiVKlSWLhwIV566SVF9uGJSpYsCYvFgkuXLqF69ero3r07/P39ERAQgBdeeAE9evTg2Fdr1G6Vyb1SU1PF2NhYcfPmzbnf69Spk7h06VLx9OnTYnZ2torVGUt8fLxosVjcepu4HTt2iN9//33u1zabTWzfvr147tw5xffdrVs3MTQ0VPH9eJrExESxSpUqYlhYmPjNN9+IgiCIs2bNEl988UXxxo0bapdHf8NLxTyMKIrw8/NDRkYGAGD79u0oXrw4nn76aVSrVi3fi5nIcYIg4LPPPsOwYcPcenFSaGgopkyZgmXLlgEA5syZg6CgIJQqVUrxfc+cORPXr1/HwoULFd+XJ4mKisK6deswbtw4DB48GCaTCQMHDsSdO3dw/vx5tcujv+HVvx4oMTERAwYMQMWKFVG8eHGUL18e48ePh5+fn9qlGUZ8fDz+9a9/qXLF74kTJ9C3b1+UKlUKISEh6N69O3r06OGWfXfv3h179+7FlStX3LI/T7V8+XJ89NFHWLduHcqUKaN2OZQHQ9VDnT9/HseOHUPFihVRtWpVBAYGql2SYQiCgKCgILz22mv4/PPPVanh2rVruHr1KipUqIASJUq47byb9L7VefPmoXfv3m7Zp5GJf3tfsSiKmDt3Lj799FMsWbIEUVFRKlZH+WGoUq60tDQsWbIEAwYMULsUXZswYQImT56Me/fuub1L1YIePXpgz5497FZddPbsWYiiiHLlyuXetEUURfz888944oknEBERoXKFlB+eU6VcO3fuxMsvv4wJEyaoXYpuCYKAzz//HMOHD1c8UG/evIm0tDS7H5+VlYU///xTwYoekM6tzp8/X/F9GdXvv/+OyMhIDB48+KHrHEwmE5o3b85A1TCGKuWKi4vDd999h48++ojB6qT4+HgIgoBJkyYpup/Tp0+jfPnymD9/PuwdNmVkZCA8PBzjx49XtLYSJUqgW7duGDVqlKL7Marff/8dtWvXRmRkJDZv3sy3zOiNOhcdk5bNmjVLNJlM4j//+U+1S9EVm80mBgQEiKNHj1Z0P6dOnRL9/PzEBg0aOHwD9Tlz5ogmk0kcN26cQtU9cPv2bdFsNos//PCDovsxmpSUFNHf31+sX78+b46vUwxVypd08H3vvffULkU33nvvPdHPz0/R96VKgdqwYUOnD7pz584VTSaTOHbsWJmre1iPHj3E0qVLK7oPI5EC9amnnmKg6hhDlQrkrq7GCGw2m+jv769olyoFaqNGjVw+6LojWKVude7cuYrtwyikQHVm+kDawlClQjFY7TNu3DhFu1Q5A1Xyww8/KB6szz//PLvVIrgyziftYahSkdw1LtQrqUsdM2aMItuXDrqNGzeW/aArBeu7774r63YlUrc6Z84cRbavd3KM80lbGKpkFwZrwZTsUk+cOCH6+fmJTZo0UeygO3/+fNFkMin2ooDdav6UmD6Q+hiqZDd3jAv1RupSlej03BGoEiWD9e7du6KXlxe71TwYqMbFUCWHKD0u1JuxY8eK/v7+sh8YT5w4IVosFrFp06ZuO+jOnz9fNJvNilxs9cILL4ilSpWSfbt6pOQ4n9THUCWHKT0u1AulutTjx4+LFotFbNasmdsPugsWLBBNJpM4atQoWbcrdauzZs2Sdbt6487pA6mDoUpOYbCK4rvvvit7l6pmoEoWLFggms1m2YP1xRdf9OhulYHqGRiq5DQlx4VaJ3Wpcp5flgL16aefVv2g+9NPP8kerFK3OnPmTNm2qRdqjPNJHQxVcolS40Ktk7tLlQI1NjZWMwddKVhHjhwp2zY9sVvVwvSB3IehSi5TalyoVTk5OaKfn59sN8RITEwULRaL+Mwzz8iyPTlJwfr222/Lsj1P61a1NH0g92CokiyUGBdq1ZgxY2TrUrUcqJJFixbJGqwvvfSSWLJkSVm2pWUMVM/EUCXZKDEu1Bo5u1Q9BKpECta33nrL5W1J3ep3330nQ2XapMVxPrkHQ5VkJfe4UGtGjx4tS5d69OhR0dfXV2zevLlMlSlPCtY33njD5W316tXLsN2qnl4skfwYqiQ7uceFWiF1qa5+HJ4eA1WyZMkSWYL13r17opeXl/jNN9/IVJk2MFCJoUqKkHNcqBWjR48WAwICXOpSpUBt0aKFjJW5l1zB2qtXL/Hxxx+XqSr1MVBJFBmqpCA5x4Vqk7rUf/7zn05v47fffhN9fX3Fli1byliZOpYuXSqazWZxxIgRTm/DSN2qnqcPJC+GKilKrq5GbaNGjXKpSzVSoErkCNbevXvrvltloFJeDFVSnN6DVepSJ06c6NTzpUBt1aqVvIVpwPLly0Wz2SwOHz7cqedL3ep///tfmStzDyOM80leDFVyCzm6GrWMHDnS6S5VCtTWrVsrUJk2SME6dOhQp57ft29fXXarRpw+kOsYquQ2egzWnJwc0WKxONWlekKgSlwJVj12qwxUKghDldzK1XGhu7399ttiYGCgw13q4cOHRR8fH7FNmzYKVaY9K1euFM1ms/j66687/Ny+ffuKjz32mAJVyc/I43xyHUOV3M7VcaG7SF1qfHy8Q8+TArVt27YKVaZdUrC+9tprDj3v3r17ore3tzh9+nSFKpOHJ00fyDkMVVKFHoLVmS7VkwNVsmrVKqeCtV+/fpruVhmoZA+GKqnGlXGh0qQu9f3337f7OQcPHhR9fHzEdu3aKViZPjgTrGlpaaK3t7f49ddfK1iZczxxnE/OYaiSqpwdFyrtrbfecqhLlQK1ffv2ClemH1KwDhkyxO7n9O/fX3PdKqcP5AiGKqnO2XGhUhztUhmoBVuzZo1Dwaq1bpWBSo5iqJImaClY33jjDbu71AMHDog+Pj5ihw4d3FCZPknB+uqrr9r1+P79+4shISEKV1U0jvPJGQxV0gxnxoVyy8rKEi0Wi/jhhx8W+VgpUDt27OiGyvRt3bp1otlsFl955ZUiHyt1q9OmTXNDZfnj9IGcxVAlTXF0XCg3e7vUAwcOiN7e3gxUBzgSrAMGDFCtW2WgkisYqqQ5jo4L5ZKVlSX6+vqKH330UaGP27dvn+jt7S3GxcW5qTLjkIJ10KBBhT5O6lanTp3qpsoe4DifXMVQJU1ypKuRy4gRI8RixYoV2qVKgdqpUye31WU069evF81mszhw4MBCHzdw4EC3dqsc55McGKqkWfZ2NXKwp0tloMpHCtYBAwYU+Bh3dqsc55NcGKqkae4K1uHDhxfape7du1f09vYWO3furGgdnsSeYB04cKBYokQJRevgOJ/kxFAlzbN3XOgsqUv95JNP8v25FKhdunRRZP+ebOPGjYUGa0ZGhujt7S1++eWXiuyf0weSG0OVdMGersZZhXWpDFTlbdy4UfTy8hL79++f788HDRqkSLfKQCUlMFRJN5QIVqlLnTRp0iM/2717NwPVTTZv3lxgsErd6hdffCFmZGSIv/32m8v74ziflMJQJV0palyYH5vNJubk5OT+ytuRDh06VAwKCnqkS5UCtWvXrrLVToWTgrVfv36P/GzAgAGij4+PaDabRV9f39zvF7a2BeH0gZTkDSIdadeuHdavX4+4uDiIoog5c+ZAEARcv34doaGhuY+zWq3IysqC1WqFKIqPbMdkMsFsNiMhIQHjxo2D2WzO/dmePXvQvHlzPPvss1i+fLlb/r8IaNOmDTZs2IAOHTpAFEXMmzcPADBq1CjMmzcPgiAAACIiIpCWllbo2np7e8NiscDb++FDXEJCAmJjYxEXF4eVK1cq/z9FHsck5ve3kkjjtmzZgg4dOqBXr15ISUnBgQMHkJ6eDh8fH6Snp8NmsxW5DZvNhqysLBQrVgyBgYHw8vLC7t270aJFCwaqirZt24Z27dqhV69eOHPmDBISEgAAVatWxbfffouaNWsiICDArm15eXkhICAAXl5euS+WGKikJJMG7CcAAAZvSURBVIYq6damTZvQvn373K/Xrl2Lpk2bOr29y5cvo06dOujcuTOWLVsmR4nkpG3btqF169a5X3/++ed48cUXYbFY4OXl5fD2rly5gujoaHTq1AkrVqyQs1Sih5iLfgiRNn344Ye5v4+Pj0fdunVd2l6JEiUwb948BqoGvP/++7m/j4+Px4svvpjbcTojODgY8+bNY6CS4tipkm6VL18ely5dwuDBgzFhwgQEBgbKsl0/Pz/4+fnJsi1yToUKFXDx4kWuLekOQ5V07dKlS/D19YWvr6+s2w0KCnK6KyJ5cG1Jjzj+JV0LDg6W/aALAOnp6bJvkxzDtSU9YqiSblmt1iKv8hVFEdHR0QgJCUFISAiSk5Pt2rbNZoPVapWjTHJCYWu7evVqhISEoHLlyrh69SqAB+vVunVrhISEYNy4cYVum2tLSmKokm5lZWUV+Zi9e/fi4sWLuV8vWrRI1u1r0RdffIHIyEhERUXhpZdeQmZmptolOaywP/vOnTuja9euuHPnDkaOHAkAmD59Og4fPozKlSvjvffec2n7RK5gqJJu2dNtLF68GAAQHR0NAFi6dGm+Nwxwdvta88cff2Dq1Kk4dOgQjh8/DpvNhp9++kntshxW1J/95MmTUbJkSWzYsAGfffYZJk2aBJPJhGnTptn1HlY9ri3pA0OVdEkQhCLDMSsrC6tWrQIAfPTRRyhRogQuXryIvXv32rUPURRz7+KjJ1arFRkZGbBarUhPT0dYWJjaJdklNjYWfn5+mDJlSpFrW7JkSXz22WcAgEmTJiEjIwODBg2y+33Kel1b0j6GKumSPQfETZs24e7duyhVqhSaNm2Kdu3aAfire7VHTk4OrFarJn/ZbLZHwqds2bIYNWoUKlSogDJlyiA4OBht27bN/bkoiqrXXdCva9euISsrCwsXLkRqamqRa9O5c+eHXjAMHjzY7nUF7Ps7ROQohioZlhSe7du3h9lsRqdOnQAAK1eutOuc2t27d9GiRQv4+Pho8tdbb731yPnS27dvY9WqVTh79iwuX76MtLQ0zJ8/P/fnFy5cUL3ugn6lpKQAACwWi10j+q+//hqXL1+GyWQCALvOpRIpjaFKhnTnzh1s2bIFAPDDDz8gJCQEffv2BQCkpqZi48aNRW4jODgYu3btgvjg05w092vatGnw9/d/qOatW7eicuXKKFWqFHx8fPDcc889NO6uWLGi6nUX9Cs8PBzAg7G9FJQFOXPmTO551NmzZ6NkyZLYvHmzLs8fk7EwVEmX8n6qTH5WrFiB7OxsBAUFoWPHjrm/qlatCsD+q4CL2o/WVKhQAfv27UN6ejpEUcS2bdsQERGhdll2CQ0NhZ+fH/r27YvixYsX+DhBEDB8+HBkZmZi0KBB6NKlCyZPngwAGDt2LK5du2bX/vS2tqQPvKMS6dbdu3cLHBN27NgRCQkJGDFiBD744IPc7+/ZswedOnWCj48PTp06hccee6zA7ZtMJgQHB8tet9ImTpyIRYsWwdvbG08++SRmzpwJi8WidlkOKWxtZ8yYgXHjxqF8+fLYu3cvihUrBgDo378/Vq9ejbi4uIdG3vnR69qS9jFUSbfS0tKQk5Oj2PZ9fHxku+csOYZrS3rF+QfpltLdl966OyPh2pJeMVRJt7y9vRW7MbqXlxe8vb0V2TYVjWtLesVQJV2z5+45Wtou2Y9rS3rEUCVd8/Lykv3zMf38/PjRYBrAtSU9YqiS7vn5+cl2jsxisfBDrDWEa0t6w6t/yTAyMzNd+kQWPz8/HnQ1imtLesFQJUOx2WxIT08v8nNW8/Ly8kJAQADHghrHtSU9YKiSIVmtVmRlZcFqteZ7EwGTyQRvb29YLBZeCaozXFvSMoYqGZ4gCA99IonZbOYt6gyCa0taw1AlIiKSCV/SERERyYShSkREJBOGKhERkUwYqkRERDJhqBIREcmEoUpERCQThioREZFMGKpEREQyYagSERHJhKFKREQkE4YqERGRTBiqREREMmGoEhERyYShSkREJBOGKhERkUwYqkRERDJhqBIREcmEoUpERCQThioREZFMGKpEREQyYagSERHJhKFKREQkE4YqERGRTBiqREREMmGoEhERyYShSkREJBOGKhERkUwYqkRERDJhqBIREcmEoUpERCQThioREZFMGKpEREQyYagSERHJhKFKREQkE4YqERGRTP4Pz3K2/PS0bBsAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Import the libraries that we are going to use, Network x to import the \n",
    "\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "\n",
    "\n",
    "# Create an empty directed graph structure: \n",
    "G = nx.DiGraph()\n",
    "\n",
    "# Add edges and define two attributes, production and costs:\n",
    "G.add_edges_from([(\"S\", \"A\", {\"capacity\": 8, \"cost\": 0}),\n",
    "    (\"S\", \"B\", {\"capacity\": 5, \"cost\": 0}),\n",
    "    (\"S\", \"C\", {\"capacity\": 3, \"cost\": 0}),\n",
    "    (\"A\", \"X\", {\"capacity\": 8, \"cost\": 45}),\n",
    "    (\"A\", \"Y\", {\"capacity\": 8, \"cost\": 45}),\n",
    "    (\"A\", \"Z\", {\"capacity\": 8, \"cost\": 45}),\n",
    "    (\"B\", \"X\", {\"capacity\": 5, \"cost\": 45}),\n",
    "    (\"B\", \"Y\", {\"capacity\": 5, \"cost\": 45}),\n",
    "    (\"B\", \"Z\", {\"capacity\": 5, \"cost\": 45}),\n",
    "    (\"C\", \"X\", {\"capacity\": 3, \"cost\": 45}),\n",
    "    (\"C\", \"Y\", {\"capacity\": 3, \"cost\": 45}),\n",
    "    (\"C\", \"Z\", {\"capacity\": 3, \"cost\": 45}),\n",
    "    (\"X\", \"T\", {\"capacity\": 5, \"cost\": 0}),\n",
    "    (\"Y\", \"T\", {\"capacity\": 4, \"cost\": 0}),\n",
    "    (\"Z\", \"T\", {\"capacity\": 3, \"cost\": 0})])\n",
    "\n",
    "# Draw the directed graph\n",
    "pos = {\"S\": (0, 1),\n",
    "       \"A\": (1, 0),\n",
    "       \"B\": (1, 1),\n",
    "       \"C\": (1, 2),\n",
    "       \"X\": (2, 0),\n",
    "       \"Y\": (2, 1),\n",
    "       \"Z\": (2, 2),\n",
    "       \"T\": (3, 1)   \n",
    "      }\n",
    "\n",
    "nx.draw(G, pos)\n",
    "nx.draw_networkx_edges(G, pos, weight=2)\n",
    "nx.draw_networkx_nodes(G, pos, node_size=600, node_color='#efefef')\n",
    "nx.draw_networkx_labels(G, pos, font_weight='bold' )\n",
    "\n",
    "cap = nx.get_edge_attributes(G, 'capacity')\n",
    "nx.draw_networkx_edge_labels(G, pos, edge_labels=cap)\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "maximum flow value: 12\n",
      "flow from  S  to  A :  4 ; Cost:  0 total cost:  0\n",
      "flow from  S  to  B :  5 ; Cost:  0 total cost:  0\n",
      "flow from  S  to  C :  3 ; Cost:  0 total cost:  0\n",
      "flow from  A  to  X :  0 ; Cost:  0 total cost:  0\n",
      "flow from  A  to  Y :  1 ; Cost:  45 total cost:  45\n",
      "flow from  A  to  Z :  3 ; Cost:  135 total cost:  180\n",
      "flow from  B  to  X :  2 ; Cost:  90 total cost:  270\n",
      "flow from  B  to  Y :  3 ; Cost:  135 total cost:  405\n",
      "flow from  B  to  Z :  0 ; Cost:  0 total cost:  405\n",
      "flow from  C  to  X :  3 ; Cost:  135 total cost:  540\n",
      "flow from  C  to  Y :  0 ; Cost:  0 total cost:  540\n",
      "flow from  C  to  Z :  0 ; Cost:  0 total cost:  540\n",
      "flow from  X  to  T :  5 ; Cost:  0 total cost:  540\n",
      "flow from  Y  to  T :  4 ; Cost:  0 total cost:  540\n",
      "flow from  Z  to  T :  3 ; Cost:  0 total cost:  540\n",
      "Total cost is:  540\n"
     ]
    }
   ],
   "source": [
    "max_flow, flow= nx.maximum_flow(G, \"S\", \"T\", capacity='capacity')\n",
    "costs = nx.get_edge_attributes(G, 'cost')\n",
    "cost=0\n",
    "print(\"maximum flow value:\", max_flow)\n",
    "for k,v in flow.items():\n",
    "    for k2 in v.keys():\n",
    "        cost+=v[k2]*costs[(k,k2)]\n",
    "        print(\"flow from \", k, \" to \", k2, \": \", v[k2], \"; Cost: \", v[k2]*costs[(k,k2)], \"total cost: \", cost)\n",
    "\n",
    "print (\"Total cost is: \", cost)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "from IPython.display import display, Markdown\n",
    "\n",
    "flow_df = pd.DataFrame.from_dict(flow, orient='index')\n",
    "display(flow_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "optimal_flow = {}\n",
    "for k,v in flow.items():\n",
    "    for k2 in v.keys():\n",
    "        optimal_flow[k,k2] = flow[k][k2]\n",
    "\n",
    "nx.draw(G, pos)\n",
    "nx.draw_networkx_edges(G, pos, weight=2)\n",
    "nx.draw_networkx_nodes(G, pos, node_size=600, node_color='#efefef')\n",
    "nx.draw_networkx_labels(G, pos, font_weight='bold' )\n",
    "nx.draw_networkx_edge_labels(G, pos, edge_labels=optimal_flow)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}